package 剑指offer;

import SortAlgotithm.QuickSort;

/**
 * Created by lenovo】 on 2017/3/8.
 */
public class FindMoreThanHalfNumFromArray {
    public int MoreThanHalfNum_Solution(int [] array) {
        int len = array.length;
        int num = 0;
        if (len == 1) {
            return array[0];
        }
        QuickSort quickSort = new QuickSort();
        quickSort.QuickSort(array , 0 , len - 1);
        int temp = array[0];
        int count = 0;
        int half = len / 2;
        for (int i = 1 ; i < len ; i ++ ) {
            if (array[i] == temp) {
                count ++;
                if (count + 1 > half) {
                    num = temp;
                    break;
                }
            }else {
                count = 0;
                temp = array[i];
            }
        }
        return num;
    }
}
